The Hadamard matrix and related Hadamard transform are mathematical techniques that have been known for over one hundred years. Jacques Hadamard published his original work in 1893 and work in similar areas was published by Rademacher in 1922 and Walsh in 1923. The origins of the Hadamard matrix, however, go back at least to 1867 when Sylvester published an early construction of what would later be known as the Hadamard matrix.
The term Hadamard transform is meant to denote any transformation of an N×1 vector by an N×N matrix HN with elements +1 and −1 that satisfies the followingHNHNT=NIN  (1)where IN is the identity matrix of order N. Matrices for arbitrary values of N can be constructed, however for certain values, the construction is non-trivial. The most convenient Hadamard matrices are of the square Sylvester type which are based on the fundamental matrix                               H          2                =                  [                                                    1                                            1                                                                    1                                                              -                  1                                                              ]                                    (        2        )            Sylvester type Hadamard matrices with N=2′ can be constructed relatively easily using the following procedure                               H                      2            n                          =                                            H              2                        ⊗            …            ⁢                                                  ⊗                          H              2                                            ︸                          n              ⁢                                                          ⁢              times                                                          (        3        )            For example, a second order Hadamard matrix H4 is given by                               H          4                =                  [                                                    1                                            1                                            1                                            1                                                                    1                                                              -                  1                                                            1                                                              -                  1                                                                                    1                                            1                                                              -                  1                                                                              -                  1                                                                                    1                                                              -                  1                                                                              -                  1                                                            1                                              ]                                    (        4        )            
Multiplying a 2-point vector x=[x0 x1]T by H2 results in the sum and difference of the two points, i.e. y=H2x.                               [                                                                      y                  0                                                                                                      y                  1                                                              ]                =                  [                                                                                          x                    0                                    +                                      x                    1                                                                                                                                            x                    0                                    -                                      x                    1                                                                                ]                                    (        5        )            This results in the radix-2 or 2-point Hadamard transform of the vector x which is the same as the 2-point discrete Fourier transform (DFT). The sum and difference operation is known as a 2-point butterfly because of the crossing flow of data from the input to output. This butterfly is used not only in the fast Fourier transform (FFT) but the fast Hadamard transform (FHT) as well.
A block diagram illustrating a prior art 2-point fast Hadamard transform butterfly structure is shown in FIG. 1. The radix-2 FHT, generally referenced 10, comprises two summations 12, 14 that receive the crossover inputs a and b. Summation 12 generates the sum component a+b and the summation 14 generates the difference a−b.
Using the Sylvester construction permits the generation of higher order Hadamard matrices by use of recursion. For any integer value n, the nth order matrix H2n has a size N×N where N=2n. Any matrix of order H2n can be generated using the recursion H2n=H2{circumflex over (×)}H2n−1 where {circumflex over (×)} denotes the Kronecker multiplication operation.
A Hadamard matrix H8 of order 3 may be constructed by cascading together three H2 transform stages as shown in FIG. 2. The implementation of the H8 transform, generally referenced 20, comprises three H2 stages comprising three columns of H2 blocks 24, 26, 28. The first stage is adapted to receive the eight input symbols 22, labeled w0 through w7. The output of the first stage 24 is input to the second stage 26 whose output is then input to the third and final H2 transform stage 28 to generate the overall output 34, labeled s0 through s7, of the H8 transform.
The second order 4×4 Hadamard matrix H4 (n=2) is generated by taking the H2 matrix and substituting H2 for each ‘1’ element, as follows                               H          4                =                  [                                                                      H                  2                                                                              H                  2                                                                                                      H                  2                                                                              -                                      H                    2                                                                                ]                                    (        6        )            A block diagram illustrating a prior art 4-point fast Hadamard transform structure constructed using radix-2 fast Hadamard transforms is shown in FIG. 3. The H4 transform, generally referenced 40, is constructed from four H2 fast Hadamard transforms 42 connected in a standard butterfly configuration. The four inputs are split into pairs and applied to two H2 transform modules that form a first stage. Similarly, a pair of outputs from each of the second stage H2 transform modules make up the four outputs.
Hadamard matrices have several useful properties resulting in their use in a wide variety of applications such as in digital communications systems like Wideband Code Division Multiple Access (W-CDMA) mobile communications systems where they are used for base to mobile (forward channel) and mobile to base (reverse channel) transmissions. Hadamard matrices and their transforms can be found in signal compression algorithms and encoding and decoding algorithms, for example.
Several properties of Hadamard matrices include: symmetry (the pth row is equal to the pth column) and orthogonality (the dot product between any two different rows equals zero). Thus, comparing any two rows results in N/2 places matching and N/2 places differing. Thus, the Hamming distance between any two rows is N/2. Hadamard matrices are also self inverting                               H          n                      -            1                          =                              1            n                    ⁢                      H            n                                              (        7        )            Another property is the sequence number of each row which indicates the number of transitions from +1 to −1 and from −1 to +1. The sequence number of a row is termed its sequency because it measures the number of zero crossings in a given interval, analogous to the frequency of a sinusoid. The sequency of a row does not necessarily match its natural order or row number.
Since the Hadamard matrix is made up of ±1s, the computation consists of additions and subtractions of the input matrix elements. Implementing the Hadamard transform using straightforward matrix multiplication, however, requires O(N2)=O(22n) operations. To speed computation, there exist many prior art Fast Hadamard transform algorithms that exploit the numerous symmetries of the Hadamard matrix. Most of the FHT algorithms require O(Nlog2N)=O(n2n) additions. The prior art algorithms do not require multiplications which make them attractive for implementation on cheap, simple digital processing hardware. In many applications, however, it would be beneficial to reduce even further the number of additions needed to implement the Fast Hadamard transform.
There is thus a need for a reduced complexity fast Hadamard transform that is efficient and low cost that requires less addition operations than prior art transforms without sacrificing accuracy and performance.